typedef char STDataType;
typedef struct Stack
{
	STDataType* _a;//标准化书写，结构体成员变量前边下划线
	int _top;//栈顶下标
	int _capacity;//容量
}Stack;
void StackInit(Stack* pst)//初始化栈
{
	assert(pst);
	pst->_a = (STDataType*)malloc(sizeof(STDataType) * 4);
	pst->_top = 0;
	pst->_capacity = 4;
}
void StackDestroy(Stack* pst)//销毁栈
{
	assert(pst);
	free(pst->_a);
	pst->_a = NULL;
	pst->_top = pst->_capacity = 0;
}
void StackPush(Stack* pst, STDataType x)//入栈
{
	assert(pst);
	if (pst->_top == pst->_capacity)
	{
		//增容
		pst->_capacity *= 2;
		STDataType* tmp = (STDataType*)realloc(pst->_a, sizeof(STDataType) * pst->_capacity);
		if (tmp == NULL)
		{
			printf("增容失败\n");
			exit(-1);
		}
		else
		{
			pst->_a = tmp;
		}
	}
	pst->_a[pst->_top] = x;
	pst->_top++;
}
void StackPop(Stack* pst)//出栈
{
	assert(pst);
	assert(pst->_top > 0);
	--pst->_top;
}
int StackSize(Stack* pst)//1、为了保持接口的一致性 2、结构体若太大，传指针好些
{
	assert(pst);
	return pst->_top;
}
int StackEmpty(Stack* pst)//返回1则表示栈空，返回0表示栈非空
{
	assert(pst);
	return pst->_top == 0 ? 1 : 0;
}
STDataType StackTop(Stack* pst)//获取栈顶的元素
{
	assert(pst);
	assert(pst->_top > 0);
	return pst->_a[pst->_top - 1];
}
bool isValid(char* s)
{
	Stack st;
	StackInit(&st);//初始化
	while (*s != '\0')//遇到左括号入栈
	{
		if (*s == '(' || *s == '[' || *s == '{')//入栈
		{
			StackPush(&st, *s);
			s++;
		}
		else//遇到右括号判断是否与栈顶元素相等然后出栈
		{
			if (StackEmpty(&st))
			{
				return false;
			}
			else {
				char ret = StackTop(&st);
				if (*s == ')' && ret == '(' || *s == ']' && ret == '[' || *s == '}' && ret == '{')
				{
					StackPop(&st);
					s++;
				}
				else
				{
					return  false;
				}
			}

		}
	}
	if (!StackEmpty(&st))
	{
		return false;
	}
	return true;
}